n=2000;
roads=[|2,1|
3,1|
4,1|
5,1|
6,1|
1,7|
1,8|
1,9|
1,10|
1,11|
12,1|
10,13|
14,8|
7,15|
16,1|
1,17|
18,1|
19,1|
20,1|
1,21|
22,1|
23,1|
24,1|
25,15|
1,26|
1,27|
28,1|
1,29|
1,30|
31,1|
17,32|
1,33|
1,34|
35,1|
1,36|
37,1|
1,38|
39,1|
40,1|
1,41|
1,42|
43,1|
1,44|
45,1|
46,1|
47,18|
48,1|
49,1|
50,1|
1,51|
1,52|
53,1|
54,1|
55,1|
1,56|
1,57|
58,35|
1,59|
60,1|
61,1|
1,62|
1,63|
30,64|
1,65|
1,66|
67,1|
68,1|
1,69|
70,1|
71,1|
1,72|
1,73|
1,74|
1,75|
1,76|
30,77|
1,78|
79,51|
80,1|
81,1|
1,82|
83,1|
84,1|
85,1|
86,1|
1,87|
88,1|
89,1|
1,90|
91,54|
92,1|
93,1|
94,1|
1,95|
1,96|
97,1|
98,68|
1,99|
100,1|
1,101|
102,1|
103,1|
104,1|
1,105|
1,106|
1,107|
1,108|
109,1|
1,110|
1,111|
112,1|
67,113|
114,1|
1,115|
1,116|
99,117|
118,1|
119,1|
69,120|
1,121|
122,1|
123,1|
124,1|
1,125|
1,126|
127,1|
1,128|
1,129|
1,130|
131,1|
90,132|
1,133|
1,134|
135,1|
136,89|
137,1|
138,3|
139,1|
140,1|
141,1|
1,142|
143,1|
1,144|
1,145|
1,146|
1,147|
1,148|
149,1|
150,1|
151,1|
1,152|
153,1|
154,1|
1,155|
1,156|
1,157|
1,158|
159,1|
160,1|
161,1|
162,89|
1,163|
1,164|
1,165|
1,166|
1,167|
1,168|
1,169|
170,125|
171,1|
172,1|
1,173|
1,174|
29,175|
1,176|
177,1|
1,178|
179,1|
180,1|
181,1|
182,1|
1,183|
98,184|
1,185|
1,186|
187,1|
1,188|
189,1|
190,1|
191,1|
192,1|
1,193|
1,194|
195,1|
196,1|
1,197|
1,198|
1,199|
1,200|
201,1|
202,1|
1,203|
204,1|
205,1|
1,206|
207,1|
1,208|
209,45|
1,210|
1,211|
1,212|
213,1|
1,214|
1,215|
216,1|
63,217|
157,218|
1,219|
54,220|
47,221|
1,222|
1,223|
224,1|
225,1|
226,1|
227,1|
228,1|
1,229|
230,1|
1,231|
232,130|
233,1|
1,234|
1,235|
236,1|
68,237|
1,238|
1,239|
240,1|
241,1|
242,1|
1,243|
1,244|
1,245|
246,1|
1,247|
248,1|
1,249|
250,1|
1,251|
1,252|
253,1|
1,254|
1,255|
1,256|
257,1|
1,258|
1,259|
260,1|
1,261|
262,1|
263,1|
264,1|
1,265|
1,266|
1,267|
1,268|
1,269|
1,270|
1,271|
272,1|
1,273|
274,1|
275,1|
1,276|
277,1|
278,1|
279,1|
1,280|
1,281|
1,282|
283,1|
1,284|
1,285|
1,286|
1,287|
1,288|
1,289|
290,1|
291,1|
291,292|
291,293|
294,291|
295,291|
296,291|
297,291|
298,291|
291,299|
300,291|
291,301|
291,302|
291,303|
291,304|
305,291|
291,306|
307,291|
308,291|
291,309|
291,310|
11,311|
312,291|
291,313|
291,314|
291,315|
144,316|
317,159|
318,291|
319,291|
320,291|
321,291|
291,322|
323,291|
291,324|
291,325|
326,291|
327,291|
328,291|
329,291|
291,330|
331,291|
316,332|
333,291|
291,334|
335,291|
336,291|
337,318|
291,338|
339,291|
279,340|
341,291|
291,342|
343,291|
291,344|
345,291|
291,346|
291,347|
348,291|
291,349|
350,291|
351,291|
291,352|
122,353|
291,354|
355,291|
291,356|
291,357|
358,291|
359,291|
291,360|
361,291|
291,362|
363,291|
291,364|
365,291|
291,366|
291,367|
368,291|
291,369|
370,291|
371,291|
372,291|
373,291|
291,374|
375,291|
291,376|
265,377|
378,291|
379,291|
380,291|
381,291|
382,291|
291,383|
291,384|
291,385|
291,386|
291,387|
291,388|
389,291|
390,291|
291,391|
291,392|
291,393|
394,291|
291,395|
291,396|
213,397|
398,291|
291,399|
291,400|
401,291|
402,291|
403,13|
291,404|
291,405|
291,406|
407,291|
344,408|
291,409|
410,291|
291,411|
412,291|
291,413|
414,291|
415,132|
328,416|
291,417|
291,418|
419,291|
420,291|
291,421|
422,291|
291,423|
291,424|
291,425|
426,291|
291,427|
291,428|
291,429|
173,430|
291,431|
432,291|
433,291|
291,434|
291,435|
436,291|
291,437|
438,115|
291,439|
440,291|
441,291|
442,291|
111,443|
444,291|
291,445|
446,291|
447,291|
448,291|
449,291|
291,450|
291,451|
452,291|
453,291|
291,454|
455,291|
456,291|
457,291|
458,406|
459,291|
460,291|
291,461|
80,462|
463,291|
291,464|
465,291|
291,466|
467,291|
398,468|
469,291|
291,470|
471,291|
444,472|
291,473|
291,474|
291,475|
291,476|
477,21|
478,291|
291,479|
480,291|
481,291|
355,482|
483,291|
484,291|
291,485|
486,291|
291,487|
291,488|
291,489|
490,291|
491,291|
492,291|
493,291|
494,88|
495,65|
496,291|
497,291|
498,291|
499,291|
291,500|
501,291|
502,291|
291,503|
504,291|
291,505|
291,506|
507,291|
508,291|
291,509|
510,291|
291,511|
291,512|
291,513|
291,514|
291,515|
516,291|
517,291|
518,291|
341,519|
520,291|
521,291|
291,522|
523,291|
524,291|
525,291|
194,526|
527,291|
172,528|
291,529|
530,291|
291,531|
532,291|
291,533|
534,291|
291,535|
536,291|
291,537|
538,291|
539,291|
540,291|
541,291|
542,291|
543,291|
544,291|
545,291|
546,291|
547,291|
291,548|
549,291|
372,550|
551,291|
291,552|
553,291|
291,554|
555,291|
291,556|
291,557|
291,558|
559,291|
560,78|
291,561|
291,562|
291,563|
564,291|
291,565|
258,566|
291,567|
568,291|
291,569|
570,291|
571,291|
572,291|
573,291|
574,195|
291,575|
576,291|
291,577|
291,578|
579,210|
291,580|
581,291|
582,291|
583,291|
584,291|
585,291|
291,586|
587,291|
291,588|
253,589|
291,590|
291,591|
592,291|
593,291|
594,291|
291,595|
291,596|
597,291|
291,598|
599,559|
291,600|
601,291|
602,291|
291,603|
291,604|
605,291|
606,291|
607,291|
608,291|
291,609|
291,610|
611,291|
291,612|
291,613|
614,447|
291,615|
616,291|
617,291|
618,291|
619,291|
620,291|
621,291|
291,622|
623,291|
624,308|
73,625|
626,291|
627,291|
628,291|
338,629|
291,630|
631,291|
291,632|
291,633|
291,634|
635,291|
291,636|
637,291|
638,291|
291,639|
640,291|
641,291|
291,642|
291,643|
644,291|
291,645|
646,291|
291,647|
648,291|
291,649|
650,291|
291,651|
291,652|
291,653|
654,291|
655,291|
291,656|
111,657|
291,658|
659,291|
660,291|
291,661|
662,291|
74,663|
664,291|
291,665|
666,291|
404,667|
668,291|
669,521|
467,670|
671,291|
672,291|
673,291|
674,291|
291,675|
676,291|
677,291|
678,291|
679,68|
291,680|
291,681|
291,682|
683,291|
684,291|
291,685|
686,291|
291,687|
291,688|
291,689|
291,690|
691,291|
692,291|
291,693|
694,291|
695,291|
291,696|
647,697|
291,698|
291,699|
700,291|
291,701|
291,702|
291,703|
291,704|
291,705|
706,291|
707,291|
708,291|
291,709|
291,710|
291,711|
712,291|
291,713|
714,291|
291,715|
716,291|
717,291|
291,718|
719,291|
720,291|
721,291|
514,722|
723,291|
724,291|
291,725|
291,726|
291,727|
728,291|
729,291|
730,291|
731,291|
291,732|
291,733|
291,734|
291,735|
291,736|
291,737|
738,291|
291,739|
740,291|
741,291|
742,291|
743,291|
744,291|
744,745|
291,746|
747,291|
291,748|
291,749|
291,750|
291,751|
291,752|
753,291|
291,754|
291,755|
756,291|
757,291|
758,291|
759,291|
760,291|
761,291|
170,762|
763,291|
287,764|
765,291|
766,85|
767,291|
291,768|
769,291|
291,770|
291,771|
772,291|
291,773|
291,774|
291,775|
776,291|
291,777|
778,291|
291,779|
780,291|
291,781|
291,782|
783,291|
291,784|
291,785|
291,786|
291,787|
291,788|
291,789|
790,291|
291,791|
291,792|
793,511|
794,291|
795,291|
291,796|
797,291|
798,291|
799,291|
291,800|
801,291|
291,802|
803,291|
804,291|
291,805|
291,806|
291,807|
291,808|
809,291|
291,810|
811,291|
291,812|
291,813|
291,814|
815,291|
291,816|
277,817|
735,818|
291,819|
291,820|
821,454|
822,291|
291,823|
824,291|
825,291|
291,826|
291,827|
828,291|
291,829|
830,291|
831,291|
832,291|
291,833|
834,605|
835,291|
836,291|
837,291|
838,291|
839,472|
291,840|
291,841|
291,842|
291,843|
844,784|
845,319|
846,793|
847,291|
848,291|
291,849|
850,291|
291,851|
852,291|
853,291|
291,854|
855,137|
856,291|
857,291|
291,858|
859,291|
860,291|
291,861|
862,390|
863,291|
291,864|
865,291|
291,866|
867,291|
868,291|
869,291|
69,870|
871,291|
291,872|
291,873|
874,291|
291,875|
291,876|
877,291|
878,291|
879,291|
880,291|
881,291|
882,291|
291,883|
884,291|
885,291|
886,291|
291,887|
888,291|
291,889|
890,291|
291,891|
892,291|
893,291|
894,291|
895,291|
291,896|
291,897|
898,291|
291,899|
291,900|
291,901|
291,902|
903,291|
291,904|
291,905|
906,291|
907,104|
908,291|
909,291|
910,291|
911,291|
912,291|
913,291|
291,914|
291,915|
916,291|
291,917|
291,918|
340,919|
291,920|
921,291|
922,291|
291,923|
291,924|
925,291|
291,926|
291,927|
291,928|
687,929|
930,563|
291,931|
932,525|
933,291|
934,816|
291,935|
936,291|
291,937|
938,291|
939,291|
291,940|
291,941|
291,942|
943,291|
944,291|
291,945|
946,291|
947,291|
291,948|
949,798|
790,950|
951,291|
952,291|
291,953|
291,954|
291,955|
291,956|
291,957|
958,291|
959,291|
291,960|
961,291|
291,962|
963,291|
964,291|
965,291|
966,59|
967,291|
291,968|
969,291|
970,291|
291,971|
291,972|
973,291|
291,974|
975,291|
976,291|
291,977|
978,291|
979,291|
291,980|
981,291|
982,291|
983,291|
291,984|
985,291|
417,986|
987,291|
988,291|
291,989|
218,990|
291,991|
992,291|
993,291|
994,291|
291,995|
291,996|
997,291|
998,291|
999,291|
291,1000|
291,1001|
1002,291|
1003,291|
291,1004|
291,1005|
291,1006|
291,1007|
291,1008|
291,1009|
1010,291|
1011,291|
1012,291|
1013,291|
291,1014|
1015,291|
291,1016|
291,1017|
291,1018|
291,1019|
291,1020|
291,1021|
1022,291|
1023,291|
1024,291|
291,1025|
1026,291|
1027,107|
291,1028|
177,1029|
1030,252|
1031,291|
1032,291|
1033,291|
291,1034|
291,1035|
291,1036|
1037,291|
291,1038|
291,1039|
291,1040|
291,1041|
291,1042|
1043,291|
291,1044|
1045,291|
291,1046|
1047,291|
1048,213|
1049,291|
1050,291|
291,1051|
291,1052|
1053,291|
291,1054|
1055,291|
1056,291|
291,1057|
1058,291|
1059,291|
291,1060|
291,1061|
1062,291|
291,1063|
291,1064|
1065,280|
291,1066|
291,1067|
1068,291|
1069,291|
1070,291|
1071,291|
291,1072|
291,1073|
1074,291|
1075,291|
1076,291|
291,1077|
1078,1058|
291,1079|
291,1080|
291,1081|
291,1082|
291,1083|
928,1084|
291,1085|
1086,291|
291,1087|
291,1088|
291,1089|
1090,291|
291,1091|
291,1092|
291,1093|
1094,291|
1095,291|
1096,291|
1097,291|
291,1098|
291,1099|
291,1100|
1101,291|
1102,291|
1073,1103|
1104,291|
1105,291|
291,1106|
291,1107|
291,1108|
291,1109|
291,1110|
291,1111|
291,1112|
1113,291|
1114,291|
1115,291|
291,1116|
291,1117|
1118,291|
1119,291|
291,1120|
291,1121|
1122,291|
1123,291|
291,1124|
291,1125|
291,1126|
1127,291|
1128,291|
291,1129|
291,1130|
291,1131|
1132,653|
1133,291|
291,1134|
1135,291|
1136,291|
291,1137|
981,1138|
1139,291|
291,1140|
1141,291|
291,1142|
1143,291|
291,1144|
291,1145|
1146,291|
291,1147|
1148,291|
291,1149|
1150,871|
1151,291|
291,1152|
158,1153|
1154,232|
1155,291|
291,1156|
291,1157|
291,1158|
291,1159|
1160,291|
1161,291|
1162,291|
291,1163|
1164,291|
1165,291|
291,1166|
291,1167|
291,1168|
1169,291|
1170,291|
1171,291|
1172,291|
1173,291|
231,1174|
291,1175|
291,1176|
291,1177|
291,1178|
1179,291|
1180,291|
1181,291|
291,1182|
291,1183|
1184,291|
291,1185|
291,1186|
1187,291|
1188,291|
1189,291|
291,1190|
1191,291|
291,1192|
291,1193|
1194,291|
291,1195|
291,1196|
1197,291|
1198,291|
291,1199|
291,1200|
291,1201|
1202,291|
291,1203|
1204,291|
524,1205|
291,1206|
1207,291|
291,1208|
1209,291|
1210,928|
1211,291|
291,1212|
291,1213|
1214,291|
1215,291|
1216,291|
1217,291|
291,1218|
1219,291|
291,1220|
1221,291|
1222,291|
291,1223|
291,1224|
1225,291|
301,1226|
1227,744|
1228,291|
291,1229|
291,1230|
291,1231|
1232,291|
291,1233|
291,1234|
291,1235|
291,1236|
291,1237|
1238,587|
1239,1137|
1240,291|
291,1241|
291,1242|
291,1243|
871,1244|
1245,291|
1246,291|
1247,291|
291,1248|
291,1249|
1064,1250|
291,1251|
1252,291|
1253,291|
1254,291|
291,1255|
291,1256|
1257,291|
1258,291|
1259,291|
291,1260|
1261,291|
291,1262|
1263,291|
291,1264|
1265,291|
1266,291|
291,1267|
1268,291|
291,1269|
291,1270|
291,1271|
1272,291|
291,1273|
291,1274|
1275,291|
1276,291|
1277,291|
291,1278|
1279,291|
1280,291|
291,1281|
291,1282|
1283,291|
1284,291|
1285,291|
291,1286|
291,1287|
1288,291|
1289,291|
291,1290|
1291,291|
1292,291|
291,1293|
1294,291|
112,1295|
1296,291|
291,1297|
1298,291|
1299,291|
1300,291|
291,1301|
291,1302|
1303,291|
291,1304|
1305,291|
291,1306|
291,1307|
1308,291|
1309,291|
291,1310|
1311,291|
1312,291|
1313,291|
1314,291|
1315,291|
291,1316|
1317,291|
291,1318|
291,1319|
1320,291|
1321,291|
291,1322|
1323,291|
291,1324|
1325,291|
291,1326|
1327,291|
1328,291|
99,1329|
1330,291|
291,1331|
1332,291|
291,1333|
291,1334|
1335,291|
1336,291|
1337,1218|
291,1338|
1339,291|
291,1340|
1341,291|
291,1342|
291,1343|
1344,291|
1345,291|
664,1346|
1347,291|
291,1348|
291,1349|
291,1350|
1351,784|
1352,123|
302,1353|
1354,291|
1355,291|
1356,291|
1357,291|
1358,291|
1359,291|
1360,291|
291,1361|
1362,20|
291,1363|
1364,74|
291,1365|
1366,291|
291,1367|
1368,291|
347,1369|
1370,291|
1371,291|
1372,1366|
291,1373|
1374,291|
291,1375|
291,1376|
1377,291|
291,1378|
1379,291|
355,1380|
291,1381|
291,1382|
1383,291|
291,1384|
1385,291|
1386,291|
291,1387|
1388,160|
769,1389|
1390,291|
291,1391|
1392,291|
1393,291|
1394,291|
291,1395|
291,1396|
291,1397|
291,1398|
291,1399|
291,1400|
1401,291|
1402,291|
291,1403|
291,1404|
291,1405|
1406,291|
291,1407|
291,1408|
1409,291|
1410,291|
291,1411|
291,1412|
1413,291|
291,1414|
1415,291|
1416,291|
1417,291|
291,1418|
291,1419|
1420,291|
1371,1421|
1422,291|
1423,291|
1424,291|
291,1425|
291,1426|
1427,291|
1206,1428|
291,1429|
1430,291|
1431,291|
1432,291|
1433,291|
291,1434|
291,1435|
1436,291|
1437,291|
291,1438|
291,1439|
291,1440|
291,1441|
1442,291|
1443,291|
1444,291|
291,1445|
291,1446|
1447,291|
1448,291|
291,1449|
291,1450|
291,1451|
291,1452|
1453,291|
1454,291|
291,1455|
1456,291|
291,1457|
1458,291|
291,1459|
1460,291|
291,1461|
1462,291|
1463,291|
291,1464|
1465,291|
1466,291|
291,1467|
291,1468|
1469,291|
1470,291|
1471,291|
1472,291|
1473,291|
291,1474|
291,1475|
1476,291|
291,1477|
291,1478|
291,1479|
291,1480|
714,1481|
291,1482|
1483,1192|
291,1484|
291,1485|
291,1486|
1487,506|
291,1488|
291,1489|
1040,1490|
291,1491|
291,1492|
291,1493|
1494,291|
1495,291|
1496,291|
1497,291|
291,1498|
1499,1310|
1500,291|
291,1501|
291,1502|
291,1503|
291,1504|
1505,291|
1506,291|
291,1507|
291,1508|
1509,39|
291,1510|
291,1511|
1512,291|
291,1513|
1514,291|
1515,291|
291,1516|
291,1517|
291,1518|
1519,291|
291,1520|
4,1521|
291,1522|
291,1523|
1524,291|
291,1525|
155,1526|
1527,291|
1528,291|
291,1529|
291,1530|
1531,291|
291,1532|
291,1533|
291,1534|
1535,291|
291,1536|
291,1537|
291,1538|
291,1539|
585,1540|
291,1541|
1542,291|
291,1543|
1544,291|
1545,1101|
1546,291|
1547,291|
1548,291|
1549,1548|
1550,1548|
1548,1551|
1548,1552|
1553,1548|
1554,1548|
1555,1548|
1548,1556|
1548,1557|
1548,1558|
1559,1548|
1548,1560|
1561,1548|
1562,1548|
1563,1548|
1564,1548|
1548,1565|
1548,1566|
1548,1567|
1548,1568|
1548,1569|
1548,1570|
1571,1548|
1572,1548|
1548,1573|
1548,1574|
1548,1575|
1576,1548|
1577,1548|
1578,1548|
1548,1579|
1548,1580|
1581,1548|
1582,1548|
1583,1548|
1584,1548|
1548,1585|
1586,1548|
1587,250|
1588,1548|
1548,1589|
1590,793|
1591,1548|
1548,1592|
1593,1548|
1548,1594|
1595,1548|
1596,1548|
1548,1597|
1548,1598|
445,1599|
1548,1600|
1601,1548|
1602,1548|
431,1603|
1548,1604|
1605,1548|
556,1606|
986,1607|
1548,1608|
1548,1609|
1548,1610|
1548,1611|
1548,1612|
1613,1548|
49,1614|
1615,1548|
1616,1548|
1548,1617|
1548,1618|
1619,1548|
1620,1548|
1621,1548|
1548,1622|
1623,1548|
1548,1624|
1625,1548|
1626,1548|
1627,1548|
1628,1548|
1548,1629|
1548,1630|
493,1631|
1548,1632|
1633,1548|
1634,1548|
1635,789|
1636,1548|
1548,1637|
1638,1548|
1639,1548|
1640,1548|
1641,83|
1548,1642|
1548,1643|
572,1644|
1645,1548|
1548,1646|
1647,1548|
1548,1648|
1548,1649|
1548,1650|
1548,1651|
1652,1548|
1548,1653|
1548,1654|
1548,1655|
1548,1656|
1548,1657|
1658,1548|
1659,1548|
1660,1548|
1661,1548|
1662,1548|
1548,1663|
1664,1548|
1548,1665|
1548,1666|
1667,1548|
1668,1548|
1548,1669|
1670,1548|
1671,1548|
1672,1548|
1548,1673|
1201,1674|
1548,1675|
1548,1676|
1677,1548|
1548,1678|
1679,1548|
1680,1548|
1681,1548|
1682,1548|
1683,1548|
1684,1548|
55,1685|
1548,1686|
1687,1548|
1548,1688|
1689,1548|
1548,1690|
1548,1691|
1692,1548|
1548,1693|
1694,1548|
1548,1695|
173,1696|
1697,1548|
1698,1548|
1548,1699|
1548,1700|
1701,1548|
1548,1702|
1548,1703|
1704,202|
1548,1705|
1548,1706|
1548,1707|
1708,1548|
1709,1548|
1548,1710|
1711,1548|
586,1712|
1548,1713|
1714,1548|
1715,1548|
1716,1548|
826,1717|
1548,1718|
1719,1548|
1548,1720|
1548,1721|
1548,1722|
1723,1548|
1724,1548|
1725,1548|
1027,1726|
1548,1727|
1548,1728|
1548,1729|
1730,1548|
1548,1731|
1548,1732|
1733,1548|
1548,1734|
1548,1735|
1736,1548|
1737,1548|
1548,1738|
1739,1548|
1740,1548|
1548,1741|
1742,1548|
1743,1548|
1744,1548|
1548,1745|
1746,1548|
1548,1747|
1548,1748|
1749,1548|
1548,1750|
1751,1548|
1752,1548|
1548,1753|
1754,1548|
1067,1755|
1756,1548|
1757,1548|
1548,1758|
1759,1548|
1760,1548|
1548,1761|
1762,1548|
1763,1548|
1548,1764|
1765,1548|
1766,1548|
1548,1767|
1548,1768|
1769,1548|
1548,1770|
1548,1771|
1772,1548|
1773,1548|
1548,1774|
1775,1548|
1548,1776|
1548,1777|
1548,1778|
1548,1779|
1780,1548|
1548,1781|
1782,266|
1548,1783|
1784,1548|
1785,1548|
1548,1786|
1787,1548|
1621,1788|
1789,1548|
1790,1548|
1548,1791|
1792,1548|
1793,1548|
1794,1548|
1795,1548|
1796,1548|
1548,1797|
1207,1798|
1799,1548|
1800,1548|
1548,1801|
1548,1802|
1548,1803|
1548,1804|
1805,1548|
1548,1806|
1616,1807|
1808,1548|
1809,1548|
1548,1810|
1548,1811|
1548,1812|
1548,1813|
1548,1814|
1548,1815|
1816,1548|
1548,1817|
1548,1818|
1125,1819|
1714,1820|
1548,1821|
551,1822|
1823,1548|
1824,1548|
1548,1825|
1826,1548|
1237,1827|
1828,1548|
1829,1548|
1548,1830|
1831,1548|
1832,1548|
1833,1548|
1548,1834|
1835,1548|
1548,1836|
1837,1548|
1838,1548|
1839,1548|
1840,1548|
1548,1841|
1842,1548|
1548,1843|
1844,1548|
1845,1548|
1846,1548|
1548,1847|
1848,1548|
1548,1849|
1850,1548|
1851,1548|
1548,1852|
1853,1548|
1548,1854|
1548,1855|
1856,1548|
1857,1548|
1548,1858|
1859,1548|
1860,1548|
1548,1861|
1862,1548|
1548,1863|
1548,1864|
1548,1865|
1548,1866|
1548,1867|
1647,1868|
1548,1869|
1548,1870|
1871,1548|
1872,1548|
1548,1873|
1548,1874|
1548,1875|
1876,1548|
1877,1548|
1367,1878|
1879,1548|
1548,1880|
1881,1548|
1882,1548|
1548,1883|
1518,1884|
1548,1885|
1886,1548|
1887,1548|
1888,1548|
1889,1548|
1890,1548|
1548,1891|
1548,1892|
1893,1548|
706,1894|
1895,1548|
1735,1896|
1548,1897|
1548,1898|
1899,1548|
1548,1900|
1901,1548|
1548,1902|
1548,1903|
1548,1904|
1548,1905|
1548,1906|
1004,1907|
1548,1908|
1548,1909|
1910,1548|
1911,1548|
1912,1548|
1913,1548|
1548,1914|
1915,1548|
1548,1916|
1548,1917|
1548,1918|
1919,1548|
1920,194|
1921,1749|
1548,1922|
1923,1548|
1924,1548|
1548,1925|
1548,1926|
1927,1548|
1548,1928|
1548,1929|
1548,1930|
1931,1548|
1548,1932|
1548,1933|
1548,1934|
1935,1548|
1548,1936|
1937,1736|
1938,1548|
1548,1939|
1548,1940|
859,1941|
1548,1942|
1943,1548|
1548,1944|
1548,1945|
1946,1548|
1548,1947|
1948,1548|
1548,1949|
1950,1548|
1548,1951|
1548,1952|
1548,1953|
1954,1548|
1955,1548|
1956,1548|
1957,1548|
1548,1958|
573,1959|
1960,1548|
248,1961|
1962,355|
1548,1963|
1964,1548|
1548,1965|
1966,1548|
1967,1548|
1968,1548|
1969,1548|
1970,1219|
1971,1548|
1972,1548|
548,1973|
1548,1974|
1975,225|
1548,1976|
1977,1548|
1548,1978|
1979,1548|
1980,1548|
1548,1981|
1548,1982|
1548,1983|
1548,1984|
1985,1548|
1548,1986|
1548,1987|
1988,1548|
1548,1989|
1548,1990|
1991,1548|
1992,1548|
1548,1993|
1548,1994|
1995,1548|
765,1996|
1997,1548|
1998,1548|
1999,1548|
1548,2000|];
W=[549,595,900,763,610,333,237,575,962,413,285,937,173,524,876,189,568,496,410,269,114,723,63,494,818,520,519,106,386,727,85,487,823,794,669,479,111,852,651,64,597,914,163,513,988,583,546,647,802,134,305,20,929,41,365,559,543,98,472,68,898,590,464,439,430,344,739,843,128,471,642,795,256,365,180,57,197,260,480,514,950,448,745,251,564,942,14,583,926,396,706,897,341,27,576,233,889,248,19,295,447,48,640,704,915,574,368,125,897,16,112,184,262,643,410,439,989,994,567,966,78,380,434,83,191,449,813,852,103,373,939,403,283,713,132,961,994,300,536,294,839,894,421,968,268,388,777,751,396,536,402,785,514,674,969,378,199,743,310,536,691,846,569,208,307,225,211,637,322,30,918,529,250,748,626,21,807,693,452,771,544,545,196,517,967,731,616,872,645,505,125,270,209,763,563,586,144,576,968,417,600,648,13,301,537,953,938,664,69,743,280,647,578,415,643,117,530,994,127,685,414,363,353,838,818,393,763,610,965,529,118,686,238,302,778,804,946,51,679,810,728,270,764,916,801,945,857,19,665,458,704,19,815,616,193,673,5,317,680,105,429,951,169,499,484,336,339,154,182,165,543,117,300,462,999,537,902,329,719,53,712,106,704,238,570,766,404,732,119,230,452,200,385,822,657,693,903,178,999,842,641,733,37,198,693,242,273,69,774,860,804,805,914,89,206,584,845,710,153,460,733,746,235,170,173,626,619,891,939,455,423,857,176,718,406,917,926,910,488,531,879,173,276,792,835,366,286,526,693,832,396,489,60,230,827,298,657,675,373,302,233,107,210,902,85,625,511,832,277,91,105,986,573,997,611,593,891,191,21,730,613,572,929,828,1,73,847,635,58,670,206,765,596,475,333,337,992,143,955,739,679,609,55,415,742,352,695,938,294,704,64,480,524,273,106,878,377,188,37,685,575,574,359,758,570,51,967,135,109,231,942,114,7,885,414,466,715,673,717,321,710,418,144,31,738,76,966,719,736,57,510,418,760,176,622,4,857,669,603,301,688,332,850,819,433,13,947,996,796,523,974,109,80,612,900,254,139,85,124,82,987,986,522,424,106,858,46,732,713,626,653,8,260,653,173,231,163,536,944,627,556,247,929,238,795,403,980,795,717,242,940,217,621,426,980,232,103,118,163,66,80,81,978,60,170,908,329,804,363,847,863,576,738,551,581,660,782,122,127,846,891,345,243,987,6,366,547,53,247,312,716,195,790,749,183,525,691,460,570,367,760,561,731,136,278,933,796,489,146,536,592,91,591,965,725,653,237,226,637,801,810,826,290,54,42,756,706,641,440,756,445,149,790,386,856,164,112,695,133,186,666,65,166,66,973,686,677,472,933,293,306,573,615,929,724,532,6,786,336,53,366,440,890,137,463,713,55,603,82,446,180,817,483,703,124,827,589,918,733,701,333,448,611,662,542,630,656,690,350,975,634,520,694,643,923,89,32,880,920,690,646,132,895,743,817,941,491,254,846,206,318,538,170,68,175,213,715,957,837,537,241,335,134,127,499,104,970,835,786,833,361,839,248,468,584,783,283,479,316,800,343,207,520,183,663,584,901,456,503,310,334,238,420,954,853,385,614,501,405,555,867,219,260,446,282,322,503,865,486,625,746,933,586,381,382,538,752,208,865,329,750,642,394,561,127,184,856,130,130,524,231,514,202,715,224,538,337,123,944,338,407,420,475,540,914,62,435,35,784,936,32,996,53,969,895,69,870,84,91,731,816,205,332,664,398,634,770,864,707,779,887,362,578,906,101,58,619,636,538,298,912,558,48,639,919,643,524,17,985,319,868,875,171,730,749,982,787,840,593,432,782,843,740,522,318,304,686,623,487,569,988,298,380,673,630,247,848,543,683,666,314,704,391,777,236,67,578,164,760,171,779,831,469,748,448,31,956,601,670,104,180,852,435,154,114,12,121,885,547,4,520,212,222,300,961,252,547,673,197,462,529,853,996,3,360,816,764,156,82,491,856,544,133,264,864,219,333,607,747,807,401,445,884,75,928,924,784,606,503,131,864,549,594,670,349,583,403,369,28,111,630,523,538,784,610,764,26,799,15,554,728,705,702,799,210,50,866,683,217,789,8,806,434,714,750,175,301,430,889,356,859,869,877,790,820,839,865,286,572,982,721,392,806,427,467,896,4,510,816,179,877,909,310,312,77,878,771,349,933,19,993,672,168,368,851,212,226,670,939,134,696,191,196,894,505,56,663,780,931,334,855,541,304,731,974,439,681,83,764,970,65,857,667,686,42,927,943,239,853,636,362,438,226,798,702,575,690,814,309,871,117,447,555,728,308,716,534,802,863,353,914,717,666,838,578,714,133,316,959,934,796,557,504,635,557,419,864,153,407,777,664,143,143,825,245,254,257,527,509,800,69,459,396,852,207,98,212,367,66,609,629,863,235,683,764,664,116,14,992,105,227,933,967,650,374,604,137,903,698,120,376,38,601,890,113,43,115,623,214,71,575,446,182,345,721,549,86,787,349,520,232,583,467,122,881,40,315,661,483,537,505,105,261,104,781,536,971,708,97,248,613,33,8,870,465,243,840,401,123,241,406,480,612,520,990,494,244,686,538,565,139,393,700,396,70,127,482,85,663,707,532,513,886,883,719,587,86,667,394,580,553,586,136,888,507,441,814,269,680,968,125,140,546,107,598,527,878,279,212,422,550,663,527,555,905,180,854,268,42,528,860,68,487,223,439,656,577,299,292,470,449,34,785,623,206,510,606,713,70,906,241,295,151,538,395,533,272,899,698,732,509,558,599,797,316,293,572,851,715,142,543,135,791,784,89,284,419,474,737,391,60,428,389,69,287,459,109,689,351,895,205,960,331,138,498,170,911,815,870,185,715,764,454,618,257,587,14,424,555,183,416,881,128,642,108,379,939,764,102,750,464,934,524,158,66,503,185,802,987,784,882,275,823,550,677,891,940,19,820,463,724,293,28,469,663,250,61,471,905,67,26,832,613,425,891,133,119,269,267,253,618,286,712,728,793,689,981,535,753,991,997,707,276,492,271,830,257,765,927,372,204,90,955,73,642,156,455,389,299,422,482,348,484,162,566,375,167,757,745,144,818,642,699,427,823,901,671,890,384,260,864,320,241,318,313,662,988,899,481,291,62,224,594,256,843,839,820,152,468,49,178,625,247,89,140,521,82,325,552,777,739,995,457,559,239,560,971,726,38,233,73,871,837,130,179,183,80,196,374,34,289,261,405,129,862,578,17,806,629,269,67,666,374,780,178,481,945,203,947,674,585,309,692,356,660,49,695,8,732,377,761,961,321,770,18,202,198,85,20,523,563,112,120,73,83,613,3,501,71,77,796,651,335,695,109,384,251,891,901,512,678,571,421,315,957,601,757,562,488,618,629,215,972,422,766,121,134,226,946,422,880,100,251,95,369,473,886,165,196,60,634,176,372,255,800,761,883,637,692,155,761,710,67,197,588,418,263,641,202,969,303,628,796,560,241,530,473,386,647,682,613,750,747,946,700,495,569,773,34,449,405,876,659,65,594,850,846,692,370,465,427,546,429,208,40,127,644,316,626,975,615,549,554,699,474,574,362,312,420,937,222,307,589,687,843,492,816,400,934,549,328,223,420,13,122,918,573,724,598,764,93,185,681,774,738,481,144,128,481,160,884,437,887,904,347,549,187,918,831,417,726,572,546,30,601,510,319,51,626,105,199,133,923,984,934,444,719,483,843,309,50,376,472,79,772,797,480,975,942,712,997,866,677,825,533,55,336,787,292,448,684,669,548,608,135,629,939,842,321,136,787,410,894,467,646,293,451,698,964,204,203,37,19,265,298,762,985,971,306,719,101,609,66,897,431,20,469,835,294,565,161,490,599,257,143,261,274,182,609,962,33,144,804,733,160,353,612,919,566,66,399,252,779,219,447,603,820,104,642,13,289,31,576,554,816,651,399,493,467,299,164,84,350,594,288,488,560,753,988,908,896,279,86,431,985,838,102,874,418,257,908,181,180,437,631,334,568,232,260,370,389,748,882,771,211,501,249,763,963,947,43,313,705,866,39,699,978,960,293,126,195,735,894,36,663,463,570,786,882,390,773,840,626,13,399,406,72,956,889,336,44,368,219,106,51,833,836,878,131,72,709,790,720,308,436,189,891,118,393,27,135,998,757,473,655,88,291,600,32,151,10,475,134,111,428,982,987,526,823,514,590,878,714,622,60,857,259,639,122,485,221,533,584,537,51,40,361,362,994,83,120,202,179,365,481,333,265,474,516,746,150,68,27,487,494,177,213,707,678,1000,431,782,116,70,972,434,643,725,149,990,546,134,575,449,49,362,291,386,124,69,542,479,340,800,360,84,881,399,601,407,176,15,742,327,975,706,792,140,14,297,676,233,772,612,978,676,229,619,704,470,304,83,887,140,71,280,394,571,175,30,761,52,842,800,293,977,189,950,606,978,364,187,548,337,95,334,886,955,856,14,13,334,10,534,546,441,961,568,580,423];